The problem of finding the ground state of a frustration-free Hamiltoniancarrying only two-body interactions between qubits is known to be solvable inpolynomial time. It is also shown recently that, for any such Hamiltonian,there is always a ground state that is a product of single- or two-qubitstates. However, it remains unclear whether the whole ground space is of anysuccinct structure. Here, we give a complete characterization of the groundspace of any two-body frustration-free Hamiltonian of qubits. Namely, it is aspan of tree tensor network states of the same tree structure. Thischaracterization allows us to show that the problem of determining the groundstate degeneracy is as hard as, but no harder than, its classical analog.
展开▼